package com.sunny.leetcode.二叉树;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给定一个 N 叉树，找到其最大深度。
 *
 * 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
 *
 * 例如，给定一个 3叉树 :
 *               1
 *         ——————|——————
 *        |      |     |
 *       3      2      4
 *    —— | ——
 *    |     |
 *    5     6
 *
 *  
 * 我们应返回其最大深度，3。
 *
 * 说明:
 *
 * 树的深度不会超过 1000。
 * 树的节点总不会超过 5000。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author Sunny
 * @date 2020/8/3
 */
public class _559_N叉树的最大深度 {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        } else if (root.children.isEmpty()) {
            return 1;
        } else {
            List<Integer> heights = new LinkedList<>();
            for (Node node : root.children) {
                heights.add(maxDepth(node));
            }
            return Collections.max(heights) + 1;
        }
    }

    public int maxDepth1(Node root) {
        if (root == null) {
            return 0;
        } else if (root.children.isEmpty()) {
            return 1;
        } else {
            Queue<Node> queue = new LinkedList<>();

            queue.offer(root);
            int height = 0;
            int levelSize = 1;

            while (!queue.isEmpty()) {
                root = queue.poll();
                levelSize--;

                for (Node node : root.children) {
                    queue.offer(node);
                }

                if (levelSize == 0) {
                    levelSize = queue.size();
                    height++;
                }
            }
            return height;
        }
    }
}
